//动态规划
let height = [0,1,0,2,1,0,1,3,2,1,2,1]
var trap = function(height) {
    let n = height.length
    let left = new Array(n)
    let right = new Array(n)
    left[0] = height[0]
    right[n-1] = height[n-1]
    let ans = 0
    for(let i=1;i<n;i++){
        left[i] = Math.max(left[i-1],height[i])
    }
    for(let j=n-2;j>=0;j--){
        right[j] = Math.max(right[j+1],height[j])
    }
    for(let z=0;z<height.length;z++){
        ans +=Math.min(left[z],right[z]) - height[z]
    }

return ans
}
console.log(trap(height));
